package com.leetcode.图论;

/**
 * lc_208
 * 实现前缀树（Trie）数据结构，支持插入、搜索和前缀匹配操作。
 * 每个节点包含两个属性：
 * - isEnd：标记该节点是否为一个单词的结尾
 * - next：指向子节点的数组，大小为26（对应小写字母a-z）
 */
public class Trie {

    // 标记当前节点是否为一个完整单词的结尾
    private boolean isEnd;
    // 存储子节点的数组，每个索引对应一个字母（0-25 对应 a-z）
    private Trie[] next;

    /**
     * 初始化前缀树节点
     */
    public Trie() {
        isEnd = false;
        next = new Trie[26];
    }

    /**
     * 向前缀树中插入一个单词
     *
     * @param word 要插入的单词
     */
    public void insert(String word) {
        // 从根节点开始,this为当前类的实例,所以为根节点
        Trie node = this;
        // 遍历单词的每个字符
        for (char c : word.toCharArray()) {
            // 计算字符在数组中的索引（a对应0，b对应1，依此类推）
            int index = c - 'a';
            // 如果对应索引的子节点不存在，则创建新节点
            if (node.next[index] == null) {
                node.next[index] = new Trie();
            }
            // 移动到子节点
            node = node.next[index];
        }
        // 标记最后一个字符的节点为单词结尾
        node.isEnd = true;
    }

    /**
     * 搜索前缀树中是否存在某个单词
     *
     * @param word 要搜索的单词
     * @return 如果存在返回true，否则返回false
     */
    public boolean search(String word) {
        // 从根节点开始
        Trie node = this;
        // 遍历单词的每个字符
        for (char c : word.toCharArray()) {
            // 计算字符在数组中的索引
            int index = c - 'a';
            // 如果对应索引的子节点存在，则继续移动到子节点
            if (node.next[index] != null) {
                node = node.next[index];
            } else {
                // 如果子节点不存在，说明单词不存在
                return false;
            }
        }
        // 检查最后一个字符的节点是否标记为单词结尾
        return node.isEnd;
    }

    /**
     * 搜索前缀树中是否存在以某个前缀开头的单词
     *
     * @param prefix 要搜索的前缀
     * @return 如果存在返回true，否则返回false
     */
    public boolean startsWith(String prefix) {
        // 从根节点开始
        Trie node = this;
        // 遍历前缀的每个字符
        for (char c : prefix.toCharArray()) {
            // 计算字符在数组中的索引
            int index = c - 'a';
            // 如果对应索引的子节点存在，则继续移动到子节点
            if (node.next[index] != null) {
                node = node.next[index];
            } else {
                // 如果子节点不存在，说明前缀不存在
                return false;
            }
        }
        // 只要前缀路径存在，就返回true，无需检查是否为单词结尾
        return true;
    }
}